COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00022 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a37.tex[154,phy] \today\hfill}

\def\dminus{\mathrel{\vbox{\lineskip0pt\baselineskip0pt
 \halign{\ctr{$##$}\cr
 .\cr-\cr}}}}

\bigskip

\noindent
\line{CS 254\hfill}    
\line{Prof. Robert W. Floyd    \hfil}

\bigskip
\noindent
Moore machine:
$$\vcenter{\baselineskip6pt\halign{$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\cr
f&&g&&h\cr
&a&&b\cr
i&&j&&k\cr}}$$

\bigskip\noindent
Inputs label edges, but outputs label states. A computation with $n$ inputs
has $n+1$ outputs. 

\medskip\noindent
Mealy machine:
$$\vcenter{\baselineskip6pt\halign{$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\cr
&a/g&&b/h\cr
i&&j&&k\cr}}$$

\bigskip\noindent
A computation with $n$ inputs has $n$ outputs. A~Moore machine can be transformed
as shown above to a Mealy machine, omitting the (constant) first output.
A~Mealy machine can be transformed to a Moore machine as shown below:
$$\vcenter{\baselineskip6pt\halign{$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\qquad
&$\ctr{#}$\cr
&&g&&h\cr
&a&&b\cr
i,?&&j,g&&k,h\cr}}$$

\bigskip\noindent
Generalized sequential machines: a Mealy machine, without restricting inputs
and outputs to be of length~1, and without assuming determinism.

\medskip
\noindent
A ({\it non-deterministic\/}) $gsm$ is:    

A finite set of states, $Q=\{q↓1,q↓2,\ldots\}$;

An input alphabet, $\Sigma =\{\sigma↓1,\sigma↓2,\ldots\}$;

An output alphabet, $\Delta =\{\tau↓1,\tau↓2,\ldots\}$;

A set of start states, $S\subset Q$;

A set of final states, $F\subset Q$;

A transition relation, $\delta\subset Q\times\Sigma↑*\times\Delta↑*\times Q.$

\bigskip
\noindent
A {\it computation\/} of a gsm M is a sequence
$q↓0,x↓1,y↓1,q↓1,x↓2,y↓2,q↓2,\ldots ,x↓n,y↓n,q↓n$, where 
$\langle q↓{i-1},x↓i,y↓i,q↓i\rangle$\break
$\in\delta$, $q↓0\in S$, $q↓n\in F$;
this computation has input $x↓1x↓2\cdots x↓n$,
and output $y↓1y↓2\cdots y↓n$.  The {\it input/output relation\/} $R↓M$ of~$M$ 
is the set of pairs $\langle x,y\rangle$ 
such that for some computation of~$M$, $x$~is the input 
and~$y$ is the output. The {\it input/output function\/} $Q↓M$ of~$M$ is defined by
$Q↓M(x)=\{\,y\mid (x,y)\in R↓M\,\}$.
If, for all~$x$, $|Q↓M(x)|≤1$, we may use $Q↓M(x)=$ the~$y$ 
(if any) such that $(x,y)\in R↓M$.

\medskip
\disleft 38pt::
{\bf Exercise}: Show that for every gsm, there is an equivalent one (same 
input-output relation) where if    
$\langle q,x,y,q'\rangle\in\delta$, then $|x|≤1$, $|y|≤1$.    

\medskip
\noindent
Let $\hat x$ be the reverse of string $x$.  
The {\sl dual\/} of $M$, $\widehat M$, has transition relation  
$\{\delta↓{\widehat M}=\{\langle q',\hat x,\hat y,q\rangle \mid$\break
$\langle q,x,y,q'\rangle \in\delta↓M\}$; 
its start and final state sets are 
$S↓{\widehat M}=F↓M$ and $F↓{\widehat M}=S↓M$; $\Sigma↓{\widehat M}=\Sigma↓M$
and $\Delta↓{\widehat M}=\Delta↓M$.

\medskip
\disleft 38pt::
{\bf Exercise}: Show that $\langle\hat x,\hat y\rangle$ 
is in the IO relation of $\widehat M$ iff
$\langle x,y\rangle$ is in the IO relation of $M$.

\medskip
\disleft 38pt::
{\bf Exercise}: Show that $\skew6\widehat{\widehat M}=M$.

\medskip
\noindent
The {\sl converse\/} of $M$, $M↑{-1}$, has ${\Sigma↓{M↑{-1}}}=\Delta↓M$,
${\Delta↓{M↑{-1}}}=\Sigma↓M$; ${\delta↓{M↑{-1}}}
=\{\langle q,y,x,q'\rangle |\langle q,x,y,q'\rangle\in\delta↓M\}$

\medskip
\disleft 38pt::
{\bf Exercise}: Show that $(M↑{-1})↑{-1}=M$, and $(\widehat M)↑{-1}=
\widehat{(M↑{-1})}$.

\medskip
\noindent
The {\sl composition\/} of two gsm's is a gsm whose IO relation is the product
of their IO relations.  To construct a gsm which is the composition 
$M'\cdot M''$ of~$M'$ and~$M''$, 
put $M'$ and~$M''$ in the form, according to the
above exercise, where all input and output strings have length $≤1$.  Let the
states of $M'\cdot M''$ be $Q'\times Q''$.
The transitions of $M=M'\cdot M''$ include:

\smallskip
\disleft 25pt:
(1): If $\langle q'↓1,x',a,q'↓2\rangle\in\delta'$
and $\langle q''↓1,a,x'',
q''↓2\rangle\in\delta''$,
then $\langle\langle q'↓1,q''↓1\rangle ,
x',x'',\langle q'↓2,q''↓2\rangle\rangle  
\in\delta↓M$.

\smallskip
\disleft 25pt:
(2): If $\langle q'↓1,x,\epsilon,q'↓2\rangle \in\delta'$,
then $\langle\langle q'↓1 ,q''\rangle,
x,\epsilon,\langle q'↓2,q''\rangle\rangle
\in\delta↓M$ for all $q''\in Q''$.

\smallskip
\disleft 25pt:
(3): If $\langle q''↓1,\epsilon , x,q''↓2\rangle 
\in\delta''$,
then $\langle\langle q',q''↓1\rangle,\epsilon,x,\langle q',
q''↓2\rangle\rangle\in\delta↓M$ for all $q'\in Q'$.

\medskip
\disleft 38pt::
{\bf Exercise}: define the starting and final sets of the composition, and show 
that the composition has the stated properties.

\medskip
\disleft 38pt::
{\bf Exercise}: 
Show $\widehat{M'\cdot M''}≡\widehat{M'}
\cdot\widehat{M''}$; 
$(M'\cdot M'')↑{-1}≡(M'')↑{-1}\cdot 
(M')↑{-1}$; $(M↓1\cdot M↓2)\cdot M↓3≡M↓1\cdot(M↓2\cdot M↓3)$.

\medskip
\noindent
If $1↓\Sigma$ is the machine whose IO relation is the identity relation on
$\Sigma↑*$, show $1↓\Sigma\cdot M≡M\cdot 1↓\Sigma ≡M$.  
That is, composition of gsm's (with a given alphabet for both input and output)
is a {\sl semigroup\/} with $1↓\Sigma$ as the identity (i.e., a {\sl monoid\/}).

\medskip
\noindent
A finite automaton {\sl acceptor\/} 
is a gsm without output; every element of $\delta$
is of the form $\langle q↓1,x,\epsilon,q↓2\rangle$.

\medskip
\noindent
Composition of a gsm with an FA yields an FA.  The IO relation of an FA is
$R\times\{\epsilon\}$, for any regular set $R$.  The converse of such an FA is
a {\sl generator\/} for the regular set $R$; it reads nothing and writes an
arbitrary member of $R$.

\medskip
\noindent
A {\sl filter\/} is an automaton whose transitions are all of the form
$\langle q↓1,x,x,q↓2\rangle$; its IO relation is a subset of the identity relation.  
A gsm filter passes through the members of any regular set you choose, 
and rejects all other input.

\medskip
The set of
palindromes over an alphabet of two or more characters is not regular.

\medskip\noindent
{\bf Proof.} If it is regular, take a FA generator for it. Compose with a
filter for $a↑{\ast}ba↑{\ast}$, to get $\{a↑iba↑i\}$. Compose with the
obvious transducer to get $\{a↑ib↑i\}$, known not to be regular:
contradiction.

\medskip
\noindent
To show that the intersection of two regular sets $R↓1$, $R↓2$ is regular, construct
a filter~$M↓1$ for~$R↓1$ and an~FA $M↓2$ for~$R↓2$; then $M↓1\cdot M↓2$ is an~FA
for $R↓1∩R↓2$.

\medskip
\noindent
To show that regular sets are closed under gsm mappings, let $M↓1$ generate a
regular set~$R$, and $M↓2$ be any gsm; then $M↓1\cdot M↓2$ generates the
$M↓2$-mapping of~$R$, and its converse is an~FA accepting the $M↓2$-mapping of~$R$.

\medskip
\noindent
To show regular sets closed under converse gsm mappings, we just notice that the
converse of a gsm mapping is itself a gsm mapping.

\smallskip
\noindent
The projections of the I/O relation of a gsm (the {\sl domain\/} and {\sl range\/})
are clearly regular sets.

\medskip
Automaton:  A finite set of control states, a finite sequence of
{\it memory units\/}, a~transition function, a~start state (or a set
of start states), a~set of accepting states.

Memory units: a countable set of {\it contents\/} (without loss of
generality, non-negative integers), with one designated as the
{\it initial content\/} (say, zero), a~finite set of singulary
recursive {\it transition functions\/}, and a finite set of recursive
predicates called {\it tests\/}.

\smallskip\noindent
Examples of memory units:

\smallskip
\disleft 25pt:(1):
A counter. Contents are non-negative integers. Initial content is~0.
Transition functions are $\hbox{increment}(x)=x+1$, 
$\hbox{decrement}(x)=x\dminus 1$. The test is $\hbox{zero}(x)≡(x=0)$.

\smallskip
\disleft 25pt:(2):
A stack. Contents are positive integers. Initial content is~1. Transition
functions are $\hbox{pushzero}(x)=2x$, $\hbox{pushone}(x)=2x+1$,
and $\hbox{pop}(x)=\lfloor x/2\rfloor$. The tests are
$\hbox{empty}(x)\equiv (x=1)$, $\hbox{topzero}(x)\equiv (x>1∧x\ \rm is\ even)$,
$\hbox{topzero}(x)\equiv (x>1∧x\ \rm is\ odd)$.

\smallskip
\disleft 25pt:(3):
A tape. Contents are $\langle\hbox{stack}\times (0,1)\times\hbox{stack}\rangle$;
transition functions are $\hbox{left}(x,y,z)=\langle\hbox{push}↓y(x)$,
$\hbox{top}(z),\hbox{pop}(z)\rangle$, etc. The transition function of an
automaton is a function of control state and of all tests of the devices,
giving a new control state and a transition function (which may be the
identity function) for each device.

\medskip
\noindent
If $C$ is any class of automata characterized by a set of allowed devices (e.g.,
having one stack, or having a finite number of counters), then $C$~is closed under
composition on either side with gsm's, using the natural definition of composition. 
E.g., let $C$ be the class of NPDA's; by composition with a filter for a regular
set, we find that the intersection of a regular set with a CFL is a CFL.
By using a NPDA generator for a CFL, and composing it with a gsm, we find
that the CFL's are closed under gsm mappings and converse gsm mappings.  We
similarly find that a PDA transducer maps a regular set into a CFL.

\proclaim
Theorem.  Every automaton is equivalent to a composition of gsm's and unit
automata, where a unit automaton has one device.
\par

\noindent
{\bf Proof.} Let $M↓1$ be the automaton.  Let $M↓2$ be a gsm which generates 
sequences of transitions for $M↓1$, while reading the inputs of those transitions.
Let $M↓3$, $M↓4,\ldots$, $M↓n$ be filters for the devices used by~$M↓1$.  
Let $M↓{n+1}$ be an automaton that reads transitions of~$M↓1$, while writing 
their outputs.  Then $M↓2\cdot M↓3\cdots M↓{n+1}≡M↓1$.

\proclaim
Theorem.  Every recursively enumerable set is a projection of the 
intersection of two CFL's.
\par

\noindent
{\bf Proof.} 
Let $M↓0$ be a Turing machine generating the set.  Let $M↓1$ be an equivalent
two-stack machine. The previous construction gives $M↓1\cdot M↓2\cdot M↓3\cdot M↓4$,
where $M↓1$ is a gsm generator, and $M↓2$ is a PDA filter, so $M↓1\cdot M↓2$
generates a CFL; $M↓3$ filters a CFL, so $M↓1\cdot M↓2\cdot M↓3$ generates
the intersection of two CFL's.  $M↓4$ is a projection gsm.  QED.

\medskip
\noindent
A gsm is deterministic if inputs uniquely determine transitions.
Construction of compositions can be twiddled to preserve
determinism.  A deterministic gsm has an input/output function.

\smallskip
\noindent
The {\it null\/} gsm $\emptyset$ has no states.  Under
composition, $\emptyset \cdot M≡M\cdot\emptyset ≡\emptyset$, 
where equivalence of gsm's means having the same I/O relation.

\smallskip
\noindent
We readily define $M↓1\cup M↓2$, 
$M↑*$, and $M↑+$. Define $M↓{\epsilon}$ with one state 
$q↓0\in F$, and no transitions.  Then $\emptyset +M≡M+\emptyset ≡M$, 
$\emptyset ↑*≡M↓\epsilon$,
$\emptyset ↑+≡\emptyset$, $1↑*↓{\Sigma}≡1↑+↓{\Sigma}≡1↓{\Sigma}$.  
Similarly, define $M↓1\otimes M↓2$ to have I/O relations 
$\{\,(x↓1x↓2,y↓1y↓2)\mid (x↓1,y↓1)\in R↓{M↓1},(x↓2,y↓2)\in R↓{M↓2}\,\}$.
$M↓{\epsilon}\otimes M=M\otimes M↓{\epsilon}=M$.

\smallskip
\noindent
The results above are essential to CS254 and should be remembered.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd
First draft (not published)
Spring 1984.
%revised date;
%subsequently revised.

\bye